home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 13 - 1997 (partial) / 13.02 Feb 97 / Challenge, Router Rules / RouterRules.cp < prev   
Encoding:
Text File  |  1997-01-03  |  20.2 KB  |  798 lines  |  [TEXT/R*ch]

  1. // ---------------------------------------------------------
  2. // RouterRules.cp
  3. //
  4. // Memory requirements
  5. // -------------------
  6. // About 12K of static tables. A variable amount of heap
  7. // memory. The program will run faster and/or yield
  8. // compacter results given more memory (in most cases).
  9. // The maximum amount of dynamic memory is approximately
  10. // (chunkSize+1)^chunkCount times the size of a pointer +
  11. // the number of input values times 12 bytes (the size of
  12. // BitGrpEntry). 'chunkSize' is 1, 2, 4 or 8. 'chunkCount'
  13. // is the width (in bits) of the input values / chunkSize,
  14. // rounded up. 'chunkCount' is between 4 and 32, inclusive.
  15. // 
  16. // How it works
  17. // ------------
  18. // - The values to be reduced are arranged in memory in
  19. // a number of linked lists. The program then loops 
  20. // through these lists trying to find values (with matching
  21. // masks) that differ in exactly one bit ('buddy' values). 
  22. // The value in a pair of such compatible
  23. // values that has a '1' in the only differing bit position
  24. // is thrown away and the mask of the the remaining value
  25. // is updated by clearing that bit. If, for a given value
  26. // no 'buddy' can be found, it is output and the program
  27. // continues until all the internal lists are empty.
  28. //
  29. // - The values are arranged in 'bit groups' to quickly 
  30. // locate a given value's buddy. A
  31. // bit group is identified by a number whose individual 
  32. // digits denote the number of bits set to 1 within a range
  33. // of consecutive bits in the input value. A range of 
  34. // consecutive bits is called a 'chunk'. Chunk sizes can
  35. // be 1, 2, 4 or 8. For example, an input value of 16 bits
  36. // that looks like this (chunkSize 4):
  37. // 1101 1001 0001 0111, will have group value 3213 (base 5,
  38. // since every digit denotes the number of 1's (0..4) per
  39. // bit sequence (chunk). During initialization,
  40. // all the input values are categorized using that scheme
  41. // by storing them in lists (one list for every bit group).
  42. // Pointers to the first elements (BitGrpEntry's) of these
  43. // lists are kept in the gBitGrpLists array. A particular
  44. // bit group can now be accessed using the bit group
  45. // value as an index into that array. For any given value,
  46. // to locate a buddy, only those
  47. // bit group lists have to be searched that differ by 1 in 
  48. // exactly one digit.
  49. //
  50. // - The class BitGrpMapper is responsible for the
  51. // initial categorization of the input values (through 
  52. // one of three lookup tables, depending on chunkSize).
  53. // The class also calculates and stores some
  54. // other values pertaining to the current run's chunk size.
  55. // The bulk of the base 3, 5 or 9 arithmetic (namely, when
  56. // for a given value the buddy groups have to be located)
  57. // is done in RemoveLoop(). For the chunkSize == 1 case, 
  58. // no lookup table is required because the bit group 
  59. // number is a binary number. Some of the functions have 
  60. // been optimized for the 1 bit case.
  61. // 
  62. // I think the algorithm is quite nice. However, there is
  63. // some room for improvement in the implementation.
  64. // Moreover, the style of the code could be improved - it
  65. // is not particularly readable and it doesn't make enough
  66. // use of types to make the code more expresive (basically
  67. // another one of those C turned C++ programs - I'm 
  68. // working on it).
  69. // ---------------------------------------------------------
  70.  
  71.  
  72. #define ALTER_INPUT_VALUES  1
  73.  
  74.  
  75. #include "ProvidedCode.h"
  76. #include "BitGrpMapper.h"
  77.  
  78.  
  79. // Data structs and types
  80.  
  81. enum ErrCode {     kNoErr = 0,
  82.                                 kErr = 1
  83. };
  84.  
  85. struct BitGrpEntry {
  86.     BitGrpEntry        *next;
  87.     ulng                    value;
  88.     ulng                    mask;
  89. };
  90.  
  91. typedef BitGrpEntry *BitGrpEntryPtr;
  92.  
  93.  
  94. // Prototypes
  95.  
  96. ErrCode    Init( void );
  97.  
  98. ErrCode Process( void );
  99.  
  100. long        CleanUp( void );
  101.  
  102. void        MakeComplement(     void );
  103.  
  104. void        InitBitGrpLists(  long        startValue,
  105.                                                      long        pastValue );
  106.  
  107. void        ClearMemory(             long    *p,
  108.                                                     long    blockCount );
  109.  
  110. void        ProcessLists(         void );
  111.  
  112. long         RemoveValues(         void );
  113.  
  114. void        RemoveLoop(             long                      curIdx,
  115.                                                     BitGrpEntryPtr    beforeEntry,
  116.                                                     BitGrpEntryPtr    curEntry );
  117.  
  118. void        RemoveLoop1Bit(     ulng                        curIdx, 
  119.                                                     BitGrpEntryPtr    beforeEntry, 
  120.                                                     BitGrpEntryPtr    curEntry );
  121.  
  122.                                         
  123. long        ScanAndKeep(          BitGrpEntryPtr    compareEntry,
  124.                                                   BitGrpEntryPtr    beforeEntry,
  125.                                                    ulng                        mask,
  126.                                                    ulng                        matchBit );
  127.                                                
  128. long        ScanAndRemove(         BitGrpEntryPtr    compareEntry,
  129.                                                   BitGrpEntryPtr    beforeEntry,
  130.                                                    ulng                        mask,
  131.                                                    ulng                        matchBit );
  132.                                                
  133. inline    long    Match(             BitGrpEntryPtr  compareEntry,
  134.                                                      BitGrpEntryPtr    thisEntry,
  135.                                                      ulng                        matchBit );
  136.                                  
  137. void         AddToOutput(            BitGrpEntryPtr    curEntry );
  138.                                     
  139.  
  140. // global data
  141.  
  142. long                            *gAllowedValues;
  143. long                            gNumAllowedValues;
  144. long                            gNumBits;
  145. Rule                            *gCurRule;
  146. long                            gMaxRules;
  147. long                            gRulesLeft;
  148. long                            gBlockNumAllowedValues;
  149. long                            gStartMask;
  150. long                          gAllow;
  151.  
  152. BitGrpMapper            gBitGrpMapper; // the BitGrpMapper class
  153. BitGrpEntryPtr        *gBitGrpLists; // Array of BitGrpEntry
  154.                                                                  // list headers
  155. BitGrpEntryPtr        gFirstFreeEntry;    
  156. long                            gNumBitGrpBlocks; 
  157. long                            gNumValuesInLists;
  158.                                                 
  159.  
  160. // Implementation
  161.  
  162.  
  163. // For any run, depending on the number of input values 
  164. // and the amount of available memory, various combinations
  165. // of chunkSize and gBlockNumAllowedValues are possible,
  166. // yielding different results and different execution times.
  167. // There wasn't enough time to sufficiently analyze the
  168. // program's algorithm. That's why this function contains
  169. // a lot of guessing. The while loop in Init() starts with
  170. // a small chunkSize (1 or 2) and tries to allocate the
  171. // required amount of memory. If that fails, the number
  172. // of input values processed at a time is split in half,
  173. // requiring less memory for the actual values. If that
  174. // still takes too much memory, the chunkSize is increased,
  175. // the number of values to be processed is reset and the
  176. // attempt to allocate memory is repeated.
  177. //
  178. ErrCode    Init( void )
  179. {
  180.     const long    kBitLimit = 27;
  181.     const long    kMemLimit = 1L << kBitLimit;
  182.     long                valueMem;
  183.     long                splitCount = 0;
  184.     long              chunkSize = 1;
  185.         
  186.     gBitGrpLists = NULL;
  187.     gBlockNumAllowedValues = gNumAllowedValues;
  188.     if (gNumBits > kBitLimit) chunkSize = 2;    
  189.         
  190.     while (gBlockNumAllowedValues > 0) {
  191.     
  192.         // Init gBitGrpMapper fur current chunk size
  193.         gBitGrpMapper.Init( chunkSize, gNumBits );
  194.         
  195.         if (splitCount == 0 && chunkSize != 8 &&
  196.                 gBitGrpMapper.numGrpLists / gBlockNumAllowedValues
  197.               > 60) {
  198.             // Very scarce -> Force shift to next chunk size
  199.             splitCount = 100;  
  200.             
  201.         } else {
  202.         
  203.             if ( 4 * gBitGrpMapper.numGrpLists < kMemLimit) {
  204.             
  205.                 // How many blocks of 8 BitGrpEntryPtr's?
  206.                 gNumBitGrpBlocks = gBitGrpMapper.numGrpLists/8 + 1;
  207.                 
  208.                 // How much memory for the values
  209.                 valueMem =
  210.                     gBlockNumAllowedValues * sizeof( BitGrpEntry );
  211.             
  212.                 if (valueMem < kMemLimit) {
  213.                                     
  214.                     // Allocate memory for the BitGrpEntry's
  215.                     gBitGrpLists = (BitGrpEntryPtr*)
  216.                         NewPtr(valueMem + 32 * gNumBitGrpBlocks);
  217.                                         
  218.                     // Successful allocation?
  219.                     if (gBitGrpLists) {
  220.                         gFirstFreeEntry = (BitGrpEntryPtr) 
  221.                             &gBitGrpLists[ 8 * gNumBitGrpBlocks ];
  222.                         return kNoErr;
  223.                     }
  224.                 }
  225.             }
  226.         }
  227.         
  228.         switch (chunkSize) {
  229.             case 1:
  230.                 if (splitCount>=1 || gBlockNumAllowedValues < 4) {
  231.                     gBlockNumAllowedValues = gNumAllowedValues;
  232.                     splitCount = 0;
  233.                     chunkSize = 2;
  234.                     continue;
  235.                 }
  236.             case 2:
  237.                 if (splitCount>=2 || gBlockNumAllowedValues < 4) {
  238.                     gBlockNumAllowedValues = gNumAllowedValues;
  239.                     splitCount = 0;
  240.                     chunkSize = 4;
  241.                     continue;
  242.                 }
  243.             case 4:
  244.                 if (splitCount>=3 || gBlockNumAllowedValues < 4) {
  245.                     gBlockNumAllowedValues = gNumAllowedValues;
  246.                     splitCount = 0;
  247.                     chunkSize = 8;
  248.                     continue;
  249.                 }
  250.         }
  251.  
  252.         gBlockNumAllowedValues /= 2;
  253.         splitCount++;
  254.     }
  255.  
  256.     return kErr;
  257. }
  258.  
  259.  
  260. // If the number of allowed values in the input exceeds
  261. // half the maximum number of allowed values (plus some
  262. // slack), the number of values that are not in the
  263. // gAllowedValues array are calculated and replace the
  264. // values in gAllowedValues. These values are then to be
  265. // denied.
  266. //
  267. void    MakeComplement( void )
  268. {
  269.     ulng    *bitMap;
  270.     ulng    numLongs = (1L << gNumBits) / 32;
  271.     
  272.     bitMap = (ulng*) NewPtr( 4 * (numLongs + 8));
  273.     
  274.     if (bitMap) {    
  275.                 
  276.         // Clear bitMap
  277.         ClearMemory( (long*)bitMap, (numLongs + 8) / 8 );
  278.     
  279.         // For every allowed value set its bit in bitMap
  280.         ulng *pastVal=(ulng*)&gAllowedValues[gNumAllowedValues];
  281.         ulng *curVal = (ulng*)gAllowedValues;
  282.         
  283.         do {
  284.             bitMap[*curVal>>5] |= (1L << (*curVal & 0x0000001f));
  285.             curVal++;
  286.         } while (curVal != pastVal);
  287.  
  288.         // Determine the values to be denied by looking for
  289.         // 0 bits in bitMap. Write them out to gAllowedValues
  290.         ulng *curEntry = bitMap;
  291.         ulng curIndex; // into bitMap
  292.         ulng curBit;
  293.         curVal = (ulng*)gAllowedValues;
  294.         
  295.         for (curIndex = 0; curIndex<numLongs; curIndex++) {
  296.             if (*curEntry != 0xffffffff) {
  297.                 for (curBit = 0; curBit<32; curBit++) {
  298.                     if ((*curEntry & (1L << curBit)) == 0) {
  299.                         *curVal = (curIndex << 5) | curBit;
  300.                         curVal++;
  301.                     }
  302.                 }
  303.             }
  304.             curEntry++;
  305.         }
  306.         
  307.         // Set the new number of values in gAllowedValues 
  308.         // and flip the gAllow variable from kAllow to kDeny
  309.         gNumAllowedValues = curVal - (ulng*)gAllowedValues;
  310.         gAllow = kDeny;
  311.         
  312.         DisposPtr( (char*) bitMap );
  313.     }
  314. }
  315.  
  316.  
  317. // Initialization of the internal lists by reading
  318. // values from gAllowedValues and storing them as
  319. // BitGrpEntry items.
  320. //
  321. void    InitBitGrpLists( long        startValue,
  322.                                              long        pastValue )
  323. {    
  324.     long                        *curVal = &gAllowedValues[startValue];
  325.     long                *pastVal = &gAllowedValues[pastValue];
  326.     BitGrpEntryPtr    curEntry = gFirstFreeEntry;
  327.     BitGrpEntryPtr    *curHead;
  328.     
  329.     ClearMemory( (long*)gBitGrpLists, gNumBitGrpBlocks );
  330.     
  331.     // Two times the same while loop. Once for the special
  332.     // case of chunkSize == 1 and then for the general
  333.     // case of chunkSize == 2, 4 or 8. Only the chunkSize
  334.     // == 2, 4 and 8 cases need gBitGrpMapper's LookUp method
  335.     // since these cases deal with base 3, 5 and 9 integers,
  336.     // respectively.
  337.     
  338.     if (gBitGrpMapper.chunkSize == 1) {
  339.         while (curVal < pastVal) {
  340.             gBitGrpLists[ *curVal ] = curEntry;
  341.             curEntry->next = NULL;
  342.             curEntry->value = *curVal;
  343.             curEntry->mask = gStartMask; 
  344.             curEntry++;
  345.             curVal++;
  346.         }
  347.     } else {
  348.         while (curVal < pastVal) {
  349.             curHead = 
  350.                 &gBitGrpLists[ gBitGrpMapper.LookUp( *curVal ) ];
  351.             curEntry->next = *curHead;
  352.             curEntry->value = *curVal;
  353.             curEntry->mask = gStartMask; 
  354.             *curHead = curEntry;
  355.             curEntry++;
  356.             curVal++;
  357.         }
  358.     }
  359.     
  360.     gNumValuesInLists = pastValue - startValue;
  361.  
  362.  
  363. // Unfortunately I don't know the PPC processors well
  364. // enough to know whether the way this loop is unrolled
  365. // really helps much.
  366. //
  367. void    ClearMemory(     long    *p,
  368.                                         long    blockCount )
  369. {
  370.     while (blockCount--) {
  371.         *p = NULL;
  372.         p++;
  373.         *p = NULL;
  374.         p++;
  375.         *p = NULL;
  376.         p++;
  377.         *p = NULL;
  378.         p++;
  379.         *p = NULL;
  380.         p++;
  381.         *p = NULL;
  382.         p++;
  383.         *p = NULL;
  384.         p++;
  385.         *p = NULL;
  386.         p++;
  387.     }
  388. }
  389.  
  390.  
  391. // Add a value for which no 'buddy' can be found to the
  392. // output array.
  393. //
  394. inline void AddToOutput(    BitGrpEntryPtr    curEntry )
  395. {
  396.     if (gRulesLeft) {
  397.         // Add to output rules
  398.         gCurRule->value = curEntry->value;
  399.         gCurRule->mask = curEntry->mask;
  400.         gCurRule->allow = gAllow;
  401.         gCurRule++;
  402.         gRulesLeft--;
  403.     }
  404. }
  405.  
  406.  
  407. // Entry point for the main processing loop. If there is
  408. // enough memory, all the available values are considered
  409. // at the same time. If memory is low, the input values
  410. // are processed in blocks of size gBlockNumAllowedValues
  411. // (likely to produce a higer number of output rules).
  412. //
  413. ErrCode Process( void)
  414. {        
  415.     long    numValuesLeft = gNumAllowedValues;
  416.     long    startValue = 0;
  417.     long    pastValue = 0;
  418.     
  419.     while (numValuesLeft) {
  420.                 
  421.         pastValue += gBlockNumAllowedValues;
  422.         if (pastValue > gNumAllowedValues) {
  423.             pastValue = gNumAllowedValues;
  424.         }
  425.         InitBitGrpLists( startValue, pastValue );
  426.         ProcessLists();
  427.         if (gRulesLeft <= 0) return kErr; // Output array full
  428.         numValuesLeft -= pastValue - startValue;
  429.         startValue = pastValue;
  430.     }
  431.     
  432.     return kNoErr;
  433. }
  434.  
  435.  
  436. // Loop over gBitGrpLists while there are values 
  437. // to combine.
  438. //
  439. void ProcessLists( void )
  440. {
  441.     while (gNumValuesInLists) {
  442.         gNumValuesInLists -= RemoveValues();
  443.     }
  444. }
  445.  
  446.  
  447. // One loop over gBitGrpLists, combining pairs of values
  448. // that differ in exactly one bit. If for a given value
  449. // such a compatible value is found (referred to as 'buddy'
  450. // in many places in the code), they are combined. This is
  451. // done by 'throwing away' the value that has a '1' in 
  452. // the bit position that differs and then clearing the
  453. // same bit in the remaining value's mask.  
  454. //
  455. long RemoveValues( void )
  456. {
  457.     long                        valuesRemoved = 0;
  458.     long                        curIdx = 0;
  459.     BitGrpEntryPtr    beforeEntry;
  460.     BitGrpEntryPtr    curEntry;
  461.     BitGrpEntryPtr    *curList     = gBitGrpLists;
  462.     BitGrpEntryPtr    *pastList = 
  463.         &gBitGrpLists[ gBitGrpMapper.numGrpLists ];
  464.  
  465.     if (gBitGrpMapper.chunkSize == 1) {
  466.  
  467.         while (curList < pastList) {
  468.             if (*curList) {    
  469.                 beforeEntry = (BitGrpEntryPtr)curList;
  470.                 curEntry = *curList;
  471.                 RemoveLoop1Bit( curIdx, beforeEntry, curEntry );
  472.                 valuesRemoved++;
  473.             }
  474.             curList++;
  475.             curIdx++;
  476.         }
  477.         
  478.     } else {
  479.         
  480.         while (curList < pastList) {
  481.             if (*curList) {
  482.                 beforeEntry = (BitGrpEntryPtr)curList;
  483.                 curEntry = *curList;    
  484.                 do {
  485.                     RemoveLoop( curIdx, beforeEntry, curEntry );
  486.                     valuesRemoved++;
  487.                     if (beforeEntry->next == curEntry) {
  488.                         beforeEntry = curEntry;
  489.                     }
  490.                     curEntry = curEntry->next;
  491.                 } while (curEntry);
  492.             }
  493.             curList++;
  494.             curIdx++;
  495.         }
  496.     }
  497.     
  498.     return valuesRemoved;
  499. }
  500.  
  501.  
  502. // RemoveLoop deals with chunkSize == 2, 4 and 8. This
  503. // Function loops over curEntry's buddy lists (lists that
  504. // may contain values that, compared with the value in
  505. // curEntry, differ in exactly one bit).
  506. //
  507. void    RemoveLoop( long                      curIdx,
  508.                                     BitGrpEntryPtr    beforeEntry,
  509.                                     BitGrpEntryPtr    curEntry )
  510. {    
  511.     short                        curChunk = gBitGrpMapper.chunkCount;
  512.     ulng                        mask = gBitGrpMapper.firstMask;
  513.     ulng                        matchBit = gBitGrpMapper.firstMatchBit;
  514.     long                        magIdx = curIdx;
  515.     long                      magStep;
  516.     ulng                        scanVal;
  517.     BitGrpEntryPtr    *buddyList;
  518.         
  519.     while (curChunk) {
  520.         
  521.       scanVal = curEntry->value & ~mask;     
  522.         magStep = gBitGrpMapper.lbTable[curChunk];
  523.         if (magIdx < gBitGrpMapper.ubTable[curChunk]) {
  524.             
  525.             buddyList = &gBitGrpLists[ curIdx + magStep ];
  526.             if (*buddyList) {
  527.                 if (ScanAndRemove( curEntry, 
  528.                         (BitGrpEntryPtr)buddyList, ~mask, matchBit )) {
  529.                     
  530.                     return; // Found a 'buddy'
  531.                 }
  532.             }
  533.         }
  534.         
  535.         if (magIdx >= magStep) {
  536.             buddyList = &gBitGrpLists[ curIdx - magStep ];
  537.             if (*buddyList) {
  538.                 if (ScanAndKeep( curEntry, 
  539.                     (BitGrpEntryPtr)buddyList, ~mask, matchBit )) {
  540.                     
  541.                     // remove curEntry from list
  542.                     beforeEntry->next = curEntry->next;
  543.                     return; // Found a 'buddy'
  544.                 }
  545.             }
  546.             
  547.             do {
  548.                 magIdx -= magStep;
  549.             } while (magIdx >= magStep);
  550.         }
  551.         
  552.         mask >>= gBitGrpMapper.chunkSize;
  553.         matchBit >>= gBitGrpMapper.chunkSize;
  554.         curChunk--;
  555.     }
  556.     
  557.     // No match found -> add to output and remove from list
  558.     AddToOutput( curEntry );
  559.     beforeEntry->next = curEntry->next;
  560.  
  561. }
  562.  
  563.  
  564. // The 1 bit only version of RemoveLoop()
  565. //
  566. void  RemoveLoop1Bit ( ulng                            curIdx,
  567.                                              BitGrpEntryPtr        beforeEntry,
  568.                                              BitGrpEntryPtr        curEntry )
  569. {
  570.     ulng                        matchBit = gBitGrpMapper.firstMatchBit;
  571.     BitGrpEntryPtr    *buddyHead;
  572.     
  573.     while (matchBit) {
  574.         
  575.         if (curIdx & matchBit) {
  576.             
  577.             if (buddyHead = &gBitGrpLists[ curIdx & ~matchBit ]) {
  578.                 if ((*buddyHead)->mask == curEntry->mask) {
  579.                     (*buddyHead)->mask &= ~matchBit;
  580.                     beforeEntry->next = NULL;
  581.                     return;
  582.                 }
  583.             }
  584.             
  585.         } else {
  586.  
  587.             if (buddyHead = &gBitGrpLists[ curIdx | matchBit ]) {
  588.                 if ((*buddyHead)->mask == curEntry->mask) {
  589.                     curEntry->mask &= ~matchBit;
  590.                     *buddyHead = NULL;
  591.                     return;
  592.                 }
  593.             }
  594.         }
  595.         
  596.         matchBit >>= 1;
  597.     }
  598.             
  599.     AddToOutput( curEntry );
  600.     
  601.     beforeEntry->next = NULL;
  602. }
  603.  
  604.  
  605. // For a given value, scans through a group list and
  606. // searches for a buddy for that value. If a buddy
  607. // is found, compareEntry will be removed by 
  608. // RemoveValues().
  609. //
  610. long    ScanAndKeep(      BitGrpEntryPtr    compareEntry,
  611.                                           BitGrpEntryPtr    beforeEntry,
  612.                                            ulng                        mask,
  613.                                            ulng                        matchBit )
  614. {
  615.     BitGrpEntryPtr    thisEntry = beforeEntry->next;
  616.     ulng                        scanValue = compareEntry->value & mask;
  617.     
  618.     while (thisEntry) {
  619.         if ((thisEntry->value & mask) == scanValue) {
  620.             if (compareEntry->mask == thisEntry->mask) {
  621.                 if (Match( compareEntry, thisEntry, matchBit)) {
  622.                 
  623.                     thisEntry->mask &= ~(compareEntry->value ^
  624.                         thisEntry->value);
  625.                     return 1;
  626.                 }
  627.             }
  628.         }
  629.         beforeEntry = thisEntry;
  630.         thisEntry = thisEntry->next;
  631.     }
  632.     
  633.     return 0;
  634. }
  635.  
  636.  
  637. // Same as ScanAndKeep() except that if a buddy is found,
  638. // it is removed after the compareEntry's mask has been
  639. // updated (see RemoveValues()).
  640. //
  641. long    ScanAndRemove(     BitGrpEntryPtr    compareEntry,
  642.                                           BitGrpEntryPtr    beforeEntry,
  643.                                            ulng                        mask,
  644.                                            ulng                        matchBit )
  645. {
  646.     BitGrpEntryPtr    thisEntry = beforeEntry->next;
  647.     ulng                        scanValue = compareEntry->value & mask;
  648.     
  649.     while (thisEntry) {
  650.         if ((thisEntry->value & mask) == scanValue) {
  651.             if (compareEntry->mask == thisEntry->mask) {
  652.                 if (Match( compareEntry, thisEntry, matchBit)) {
  653.                     
  654.                     compareEntry->mask &= ~(compareEntry->value ^
  655.                         thisEntry->value);
  656.                     beforeEntry->next = thisEntry->next;
  657.                     return 1;
  658.                 }
  659.             }
  660.         }
  661.         beforeEntry = thisEntry;
  662.         thisEntry = thisEntry->next;
  663.     }
  664.     
  665.     return 0;
  666. }
  667.  
  668.  
  669. // The two values compareEntry->value and 
  670. // thisEntry->value can be combined if they differ in
  671. // exactly one bit. In those cases, refVal, below, will
  672. // have exactly one bit set. The rest of the code
  673. // tests to see if that is so. I have the feeling that
  674. // this function's efficiency could be improved.
  675. //
  676. inline long    Match(     BitGrpEntryPtr  compareEntry,
  677.                                          BitGrpEntryPtr    thisEntry,
  678.                                          ulng                        matchBit )
  679. {
  680.     ulng    refVal = compareEntry->value ^ thisEntry->value;
  681.     ulng    matchCount = 0;
  682.         
  683.     switch (gBitGrpMapper.chunkSize) {
  684.         case 2:
  685.             if (! (refVal ^ matchBit)) return 1;
  686.             matchBit >>= 1;
  687.             if (! (refVal ^ matchBit)) return 1;
  688.             return 0;
  689.         case 4:
  690.             if (! (refVal ^ matchBit)) return 1;
  691.             matchBit >>= 1;
  692.             if (! (refVal ^ matchBit)) return 1;
  693.             matchBit >>= 1;
  694.             if (! (refVal ^ matchBit)) return 1;
  695.             matchBit >>= 1;
  696.             if (! (refVal ^ matchBit)) return 1;
  697.             return 0;
  698.         case 8:
  699.             if (! (refVal ^ matchBit)) return 1;
  700.             matchBit >>= 1;
  701.             if (! (refVal ^ matchBit)) return 1;
  702.             matchBit >>= 1;
  703.             if (! (refVal ^ matchBit)) return 1;
  704.             matchBit >>= 1;
  705.             if (! (refVal ^ matchBit)) return 1;
  706.             matchBit >>= 1;
  707.             if (! (refVal ^ matchBit)) return 1;
  708.             matchBit >>= 1;
  709.             if (! (refVal ^ matchBit)) return 1;
  710.             matchBit >>= 1;
  711.             if (! (refVal ^ matchBit)) return 1;
  712.             matchBit >>= 1;
  713.             if (! (refVal ^ matchBit)) return 1;
  714.             return 0;
  715.     }
  716.     return 0;
  717. }
  718.  
  719.  
  720. // I first developped this solution using the Symantec
  721. // environment where I used the C++ new and delete
  722. // functions for memory management. After moving to 
  723. // CodeWarrior, however, I had to use the Mac Toolbox
  724. // function NewPtr to allocate memory in Init() (and 
  725. // DisposPtr to dispose of it here) because Codewarrior's
  726. // implementation of new didn't seem to reliably return
  727. // NULL in cases a memory request could not be 
  728. // satisfied.
  729. // 
  730. long        CleanUp( void )
  731. {
  732.     if (gBitGrpLists) DisposPtr( (char*)gBitGrpLists );
  733.     
  734.     if (gRulesLeft > 0) {
  735.         gCurRule->value = 0;
  736.         gCurRule->mask = 0;
  737.         if (gAllow == kAllow) {
  738.             gCurRule->allow = kDeny;
  739.         } else {
  740.             gCurRule->allow = kAllow;
  741.         }
  742.         gRulesLeft--;
  743.         
  744.         return gMaxRules - gRulesLeft;
  745.     } else {
  746.         return -1;
  747.     }
  748.     
  749. }
  750.  
  751.  
  752. // Main entry point
  753. //
  754. long RouterRules( long    allowedValues[],
  755.                                     long    numAllowedValues,
  756.                                     long    numBits,
  757.                                     Rule    rulesArray[],
  758.                                     long    maxRules )
  759. {
  760.     gAllowedValues = allowedValues;
  761.     gNumAllowedValues = numAllowedValues;
  762.     gNumBits = numBits;
  763.     gCurRule = rulesArray;
  764.     gMaxRules = maxRules;
  765.     gRulesLeft = maxRules;
  766.     gStartMask = 0xffffffff >> (32-gNumBits);
  767.     gAllow = kAllow;
  768.     
  769.     if (maxRules <= 0) return -1;
  770.     
  771.     if (numAllowedValues <= 0) {
  772.         gCurRule->mask = 0;
  773.         gCurRule->value = 0;
  774.         gCurRule->allow = kDeny;
  775.         return 1;
  776.     }
  777.     if (numAllowedValues == (1L << numBits)) {
  778.         gCurRule->mask = 0;
  779.         gCurRule->value = 0;
  780.         gCurRule->allow = kAllow;
  781.         return 1;
  782.     }    
  783.     
  784.     #if ALTER_INPUT_VALUES == 1
  785.     if (numBits > 5 && numBits < 32 && numAllowedValues > 
  786.         ( (1L<<(numBits-1)) + (1L<<(numBits-5)) )) {
  787.         MakeComplement();
  788.     }
  789.     #endif
  790.     
  791.     if (Init() == kErr) return -1;
  792.     Process();
  793.     return CleanUp();
  794. }
  795.  
  796.  
  797.